import java.util.ArrayList;
import java.util.List;

/**
 * 306. 累加数
 * https://leetcode-cn.com/problems/additive-number/
 */
public class Solutions_306 {
    public static void main(String[] args) {
//        String str = "112358";  // output: true
//        解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

//        String str = "199100199";  // output: true
//        解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

//        String str = "1203";  // output: false

//        String str = "1023";  // output: false

//        String str = "112358130";  // output:  false   最后一位数为 0，导致数组无法组成累加序列

//        String str = "0123";  // output: false

//        String str = "0000";  // output: true  0, 0, 0, 0

//        String str = "1011";  // output: true  1, 0, 1, 1

        String str = "121474836472147483648";  // output: true  1, 2147483647, 2147483648

        boolean result = isAdditiveNumber2(str);
        System.out.println(result);
    }

    /**
     * 解法二：回溯法优化版（0ms）
     */
    public static boolean isAdditiveNumber2(String num) {
        if (num == null || num.length() < 3) {
            // 特殊情况的判断
            return false;
        }
        char[] arr = num.toCharArray();
        boolean res = backtrack(arr, 0, 0, 0, 0);
        return res;
    }

    /**
     * @param arr
     * @param idx 遍历索引
     * @param sum 序列中的前两个数值之和（即当前值要等于 sum 才能组成累加序列）
     * @param pre 序列中位于当前值的前一个值（即当前值 + pre 值，成为下一个数值的 sum 值）
     * @param k 累加序列中的数值个数
     * @return
     */
    public static boolean backtrack(char[] arr, int idx, long sum, long pre, int k) {
        if (idx == arr.length) {
            // 返回结果
            return k > 2;
        }
        long num = 0;
        for (int i = idx; i < arr.length; i++) {
            // 零值的判断（首位不能为 0）
            if (i > idx && num == 0) {
                // 如果首位不为 0，那么 num 一定是大于 0 的
                break;
            }
            num = num * 10 + (arr[i] - '0');
            // 剪枝：判断整数过大的情况（暂无解决方案）
            // 仅仅使用 Integer.MAX_VALUE 判断时，若累加序列中可能有 long 值，则判断不准确
//            if (num > Integer.MAX_VALUE) {
//                break;
//            }
            if (k >= 2) {
                // 当前 num 是否是前两个数之和
                if (num > sum) {
                    // 已经大于了，不再往后走
                    return false;
                } else if (num < sum) {
                    // 还小于前两个数之和，继续往后走
                    continue;
                }
            }
            // 要么 num 等于前两个数之和，要么 num 本身就是前 2 个数，那么添加元素，并递归
            boolean res = backtrack(arr, i + 1, num + pre, num, k + 1);
            if (res) {
                // 以 num 得到的累加和，可以将 arr 数组分解为累加序列，那么不再遍历后续的可能情况
                // 直接返回 true
                return true;
            }
        }
        return false;
    }

    /**
     * 解法一：回溯法（1ms）
     */
    public static boolean isAdditiveNumber(String num) {
        if (num == null || num.length() < 3) {
            // 特殊情况的判断
            return false;
        }
        List<Long> list = new ArrayList<>();
        char[] arr = num.toCharArray();
        boolean res = backtrack(list, arr, 0);
        return res;
    }

    public static boolean backtrack(List<Long> list, char[] arr, int idx) {
        if (idx == arr.length) {
            // 返回结果
            return list.size() >= 3;
        }
        long num = 0;
        for (int i = idx; i < arr.length; i++) {
            // 零值的判断（首位不能为 0）
            if (i > idx && num == 0) {
                // 如果首位不为 0，那么 num 一定是大于 0 的
                break;
            }
            num = num * 10 + (arr[i] - '0');
            // 判断整数过大的情况
            // 仅仅使用 Integer.MAX_VALUE 判断时，若累加序列中可能有 long 值，则判断不准确
//            if (num > Integer.MAX_VALUE) {
//                break;
//            }
            if (list.size() >= 2) {
                // 当前 num 是否是前两个数之和
                long num1 = list.get(list.size() - 1);
                long num2 = list.get(list.size() - 2);
                long sum = num1 + num2;
                if (num > sum) {
                    // 已经大于了，不再往后走
                    return false;
                } else if (num < sum) {
                    // 还小于前两个数之和，继续往后走
                    continue;
                }
            }
            // 要么 num 等于前两个数之和，要么 num 本身就是前 2 个数，那么添加元素，并递归
            list.add(num);
            boolean res = backtrack(list, arr, i + 1);
            if (res) {
                // 以 num 得到的累加和，可以将 arr 数组分解为累加序列，那么不再遍历后续的可能情况
                // 直接返回 true
                return true;
            }
            // num 元素不能得到 true 值，那么移除元素
            list.remove(list.size() - 1);
        }
        return false;
    }
}
